package org.nowcoder.leetcode.DP;

/**
 * Title  : 121. Best Time to Buy and Sell Stock
 * Source : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-07-07
 */

public class LeetCode_121 {
    public int maxProfit(int[] prices) {
        //暴力解法： 超时
//        int max = 0;
//        for (int i = 0; i < prices.length - 1; i++) {
//            for (int j = i + 1; j < prices.length; j++) {
//                int profit = prices[j] - prices[i];
//                if (profit > max) {
//                    max = profit;
//                }
//            }
//        }
//        return max;

        //最优解法
        //一次遍历：计算第i天的最大收益，只需要要知道前i-1天的最低点
        int maxProfit = 0, minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (minPrice > prices[i]) {
                minPrice = prices[i];  //找到最低点
            } else if (maxProfit < prices[i] - minPrice) {
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }

    public int maxProfitDP(int[] prices) {
        //1. 定义状态： dp[i],表示前i天购入的最低点
        int[] dp = new int[prices.length];

        //2. 初始状态
        dp[0] = prices[0];
        int max = 0;

        //3. 状态转移方程
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.min(dp[i - 1], prices[i]);
            max = Math.max(max, prices[i] - dp[i - 1]);
        }
        return max;
    }
}
